模板(基础模版)

Posted on | Post modified: | In |
Words count in article: 4.4k

快速排序

  快速排序先确定一个基准点$P$，然后调整序列，使得基准点$P$左边的点小于等于$P$，右边的点大于等于$P$。这样$P$的位置便是排好序后的位置，再递归的对$P$左边和右边的子序列做同样调整（选一个新的基准点）。因此快排总结为3步：

  1. 确定基准点。可以随机选，也可以端点或中点。
  2. 调整基准点两边的数据。可左右扫描选择不满足的两个进行交换。
  3. 确定子序列，继续递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void qsort(int a[], int l, int r){
    if(l >= r) return ;
    int i = l-1, j = r+1, mid = a[l+r>>1];
    while(i < j){
        while(a[++i] < mid) ; //先移动再判断，防止相等时TLE
        while(a[--j] > mid) ; 
        if( i < j){
            swap(a[j], a[i]);
        }
    }
    //执行完成后mid两端满足一边<=mid,一边满足>=mid，继续递归让所有点满足这个约束
    // 一趟完成后j<=i,使用j作为分界点较好，用i作为分界点需要考虑边界问题，l + r + 1 >> 1, 和二分边界有些类似
    qsort(a, l, j);
    qsort(a, j+1, r);
}

归并排序

  归并排序使用分治策略，将无序序列不断二分，最终每个子序列(单个数)都是有序的。再回溯该过程，将有序的子序列合并为一个序列。

  1. 二分为两个子序列。
  2. 对两个子序列递归。
  3. 递归返回时，合并已有序的子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_sort(int a[], int l, int r){
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid+1, r);//先递归，让子序列有序
    
    int i = l, j = mid + 1, k = 0;  // 合并有序子序列
    int tmp[r-l];
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) 
            tmp[k++] = a[i++];      // tmp 保存当前两段子序列的临时合并结果
        else
            tmp[k++] = a[j++];      
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    
    for(i = l, k = 0; i <= r; i++, k++)  // tmp存储的临时有序序列还回原数组
        a[i] = tmp[k];
}

希尔排序

image-20191205222053773

拓扑排序

判环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    if (!prerequisites.size()) return true;
    vector<vector<int>> graph(numCourses);
    vector<int> indegree(numCourses);
    for(const auto &edge : prerequisites) {
        graph[edge[0]].emplace_back(edge[1]);
        indegree[edge[1]] ++;
    }

    queue<int> que;
    for (int i = 0; i < numCourses; ++ i) {
        if (indegree[i] == 0) que.push(i);
    }

    while (que.size()) {
        -- numCourses;
        int ver = que.front(); que.pop();
        for (int adj_ver : graph[ver]) {
            if (-- indegree[adj_ver] == 0) 
                que.push(adj_ver);
        }
    }
    return (numCourses == 0);
}

整数二分

  二分常常与单调有序的情况联系起来，比如二分查找。但二分的本质并不只是单调性，它可将一段数据按是否满足某条件而分为两段。用二分来找到这两段邻接的边界，当然可以是左边界，也可以是右边界。在二分查找中这个条件就是数值大小。当序列中有重复数字时，二分时区间不同得到的结果可能是不同的。这时可取左边界，也可右边界，这样分为两种情况的区间：

  1. $[l,\;mid]$ 与 $[mid+1, \; r]$
  2. $[l,\;mid-1]$ 与 $[mid, \; r]$

  这两种区间有着不同的特性，比如在二分搜索时，若使用第一种区间，可看到$mid$是偏向左端的，因此若结果有重复的多个数据，结果位置会返回较左端近的位置。于是第一种方式可以认为是查找大于等于$num$的最左端位置。

实质上二分是将序列按照某种性质分割为两个区间，常用的性质是大小。『 其中分割点属于哪个区间是比较关键的，它可以是满足左边性质的点，也可以是满足右边性质的点』。上述两个区间就是分别查找性质属于右边和左边的分割点，对于重复点，如果使用查右半边性质的方法1，那么找到的就是重复点的最左端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ##区间[l, r]被划分成[l, mid]和[mid + 1, r]时：
void bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        // check()判断mid是否满足性质，右端点始终包含mid，因此最后二分出来的点一定满足右半序列的性质。
        if (check(mid)) r = mid;    
        else l = mid + 1;
    }
}
// ##区间[l, r]被划分成[l, mid - 1]和[mid, r]时：
void bsearch_2(int l, int r)
{
    while (l < r)
    {   //注意必须+1，当l与r相邻时，l=(l+r)/2=l，此时对l的更新变成死循环。
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid; 
        else r = mid - 1;    
    }
}

  两种方法的区别可以通过下面这个题理解一下，求一串非递减序列中某个数字的存在范围，即起始位置到终止位置。当基准点$mid$两端边界更新的优先不同时，会得到满足查找数字$num$区间的不同端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main(){
    int n, c, num;
    cin>>n,cin>>c;
    int a[n+1];
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    for(int i=0; i<c; i++) {
        int l = 0, r = n-1;
        cin>>num;
        
        while(l < r){            //确定左边界
            int mid = l + r >> 1;
            if( a[mid] >= num ) r = mid;  
            else l = mid + 1;             
        }
        if(a[l] != num) cout<<"-1 -1"<<endl;
        else{          
            cout<< l <<" ";
            int l = 0, r = n-1;
            while(l < r){       //确定右边界
                int mid = l + r + 1 >> 1;  
                if( a[mid] <= num ) l = mid; //判定往右的条件
                else r = mid -1;
            }
            cout<< l<< endl;
        }
    }
    return 0;
}

大数加法

  输入数据超过64位时，便不能再使用简单数据类型保存。结果的长度未知，可用向量来动态添加。为了加法计算方便，向量中保存的数据应是逆序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> add(vector<int> a, vector<int> b){
    if(a.size() < b.size()) return add(b, a);
    vector<int> c;
    int t = 0;    //t用于加法进位
    for(int i = 0; i < a.size(); i++){
        t += a[i];
        if(i < b.size()) t += b[i];
        c.push_back(t%10);  //vector可方便的动态添加
        t /= 10;
    }
    if(t) c.push_back(t);
    return c;
}
int main(){
    string a, b;
    cin>> a>> b;
    vector<int> A, B;
    for(int i = a.size()-1; i >= 0; i--) A.push_back(a[i]-'0');//低位先填充，方便加法先计算
    for(int i = b.size()-1; i >= 0; i--) B.push_back(b[i]-'0');
    vector<int> c = add(A, B);
    for(int i = c.size()-1; i >= 0; i--) cout<< c[i];
    return 0;
}

大数减法

  减法与加法类似，只需要判断是否有借位即可。另需保证被减数A的数值大于B的数值，不能只是简单的像加法那样判断长度。减法的高位可能存在有多余的0的情况，需要去掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> sub(vector<int> a, vector<int>b){
    int t = 0;          //t用于减法借位，作为借位标志只有0,1之分
    vector<int> c;
    for(int i = 0; i < a.size(); i++){
        t = a[i] - t;   //去掉借位
        if(i<b.size()) t -= b[i] ;
        c.push_back((t+10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
//调用减法之前确定哪个数大
bool cmp(vector<int> a, vector<int> b){  
    if(a.size() != b.size()) return a.size() > b.size();
    for(int i = a.size()-1; i >= 0; i--)
        if(a[i] != b[i]) return a[i] > b[i];
    return true;
}

大数乘小数

  一个大数与一个可用基本类型表达的数作乘法，可按位将大数中的每一位与小数作乘法，再求和。

1
2
3
4
5
6
7
8
9
10
vector<int> mul(vector<int> a, int b){
    vector<int> c;
    int t = 0;   //过渡
    for(int i = 0; i < a.size() || t; i++){
        if(i < a.size()) t += a[i] * b;  //a中每位与b相乘
        c.push_back(t%10);
        t /= 10;
    }
    return c;
}

大数除小数

  除法与其它运算不同的是它从高位开始计算，余数往后扩位。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> sub(vector<int> a, int b, int &r){
    vector<int> c;
    for(int i = 0; i < a.size(); i++){
        r = r * 10 + a[i] ; //上一步的余数往后扩位
        c.push_back(r / b);
        r %= b;             //余数
    }
    reverse(c.begin(), c.end());
    while(c.size()>1 && c.back() == 0) c.pop_back();
    
    return c;
}

前缀和

  一维前缀和比较简单，公式如下

  二维前缀和与一维差不多，不过是将输入数组变为二维的矩阵形式。其公式为

这是以$(x_1,y_1)$为左上角，$(x_2,y_2)$为右下角的子矩阵的和。其前缀和的建立可图示如下：

1583339392672

  为了求解图中蓝色子矩阵的和，用这四个小矩阵组成的大矩阵，减去绿色和红色区域代表的子矩阵的和，显然它们的交叉区域多减了一次，于是加上交叉区域的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector< vector<int>> s(n+1, vector<int>(m+1, 0)); // 必须初始化为0
    
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)  
        cin>>s[i][j];  //从 1 开始录入数据
    
for(int i = 1; i<= n; i++)
    for(int j = 1; j <= m; j++)
        s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];  //构建前缀和
    
int a, b, c, d;
while(q--){
    cin>>a >> b>> c>> d;
    cout<< s[c][d] - s[a-1][d]- s[c][b-1] + s[a-1][b-1] << endl;//计算子矩阵
}

差分

  差分与前缀和关系较密切，甚至可以看作逆操作。对差分数组求前缀和可得到原始数组，同样，对前缀和求差分也能得到原数组。

  差分数组还有个特性：对原始数组$[l,\; r]$区间上的内容$+c$等价于对差分数组的这两个端点执行$d[\;l\;]+c, \;d[r+1]-c$ 。因为变回原始数组求前缀和时会将$d[l]$上多出的$c$加到$l$之后的元素上，$r$之后的不需要加$c$，因此在$r+1$处减去$c$抵消。

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++)  //构造差分数组，差分需用两个数组
    d[i] = a[i] - a[i-1] ;
	//对区间[l, r] 上的数+ c
    d[l] += c;
    d[r+1] -= c; 
	//对差分数组求前缀和得，前缀和可在原数组执行
for(int i = 1; i <= n; i++)
    d[i] = d[i-1] + d[i] ;

  对于二维差分，与一维差不多，类似于一维前缀和到二维前缀和的扩展。对于二维的图示，只需将前缀和的图片旋转180即可。

1583339704555

  对于差分矩阵，在某个点加上一个数值相当于给它右下方矩阵所有值加上这个数值，于是它的情况正好和前缀和相反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insert(vector< vector<int>> &a, int x1, int y1, int x2, int y2, int v){
    a[x1][y1] += v;
    a[x1][y2+1] -= v;
    a[x2+1][y1] -= v;
    a[x2+1][y2+1] += v;
}  //在某个子矩阵 + C ， 添加某个点也是特殊的矩阵

vector< vector<int>> a(n+5, vector<int>(m+5, 0));
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        cin>>temp;
        insert(a, i, j, i, j, temp);  //构造差分矩阵的过程看作在(1,1)矩阵上的插入过程
    }
int x1, y1, x2, y2, c;
cin>> x1>> y1>> x2>> y2>> c;
insert(a, x1, y1, x2, y2, c);     //子矩阵 + c

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
       a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];  //前缀和求原始矩阵

二进制中1的个数

  利用二进制减法的借位和按位与运算。二进制非$0$ 即 $1$，$num-1$ 时会取走$num$当前最低位的 $1$，若有借位，借位后面的$0$ 都会变成 $1$，但是与原$num$进行按位与操作后便为 $0$，这样一遍操作便取走一个 $1$，直到$num=0$ 。

1
2
3
4
5
int count = 0;
while(num){
    num = (num-1) & num;
    count ++;
}

双指针算法

双指针一般有两种思路：

  1. 对于一个序列，用两个指针维护一段区间
  2. 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

  对于第一种，需要确定的是这段区间的性质以及如何维护这段区间。例如最大无重复子串，需要维护的区间是子串，子串的性质是区间内无重复字符。那么主要的任务就是保证这段区间内的字符不重复，可以使用另一个数组来记录字符出现的次数，也可以记录字符出现的位置。若使用次数则维护次数<=1，若使用位置则保证前指针指向的字符没有出现过或是出现的位置不在子串内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int N = 1e5+10;
int s[N]={0}, h[N]={0};  //数值范围和数据量范围都是10w
int main(){
    int n, count = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    //l, r 分别记录当前合法子串左右位置
    for(int r = 1, l = 1; r <= n; ++r){   //维护新出现字符的上次出现位置不在子串内，h数组更新字符最后一次出现的位置
        if(h[s[r]] == 0 || l > h[s[r]])// 新字符未出现或出现了但未在区间内（左边界左侧）
            //注意这里使用了位置是否为0来作为是否出现的依据，因此必须从1开始存数据
            count = max(count, r - l +1);
        else
            l = h[s[r]] + 1; //子串内出现，更新左边界
        h[s[r]] = r; //更新该数值的位置
    }
    
    // for(int r = 1, l = 1; r <= n; r++){ //维护区间内字符只出现一次，h数组保存次数
    //     h[s[r]] ++;
    //     while( h[ s[r] ] > 1)
    //         h[ s[l++] ] -- ; //移动左边界，直到区间无重复字符
    //     count = max(count, r - l + 1);//
    // }
    cout << count;
    return 0;
}

  对于第二种，维护两个序列之间的某种关系。关键是找到它们之间的联系，例如求解两个升序序列中元素和为某个值的元素位置。那么目标就是计算两两之间的和，但是由于是升序，可以判断和的大小来剪去多余计算。

1
2
3
4
for(int i = 0, j = m-1; i < n; i++){ //对于第二个数组从后往前遍历
    while( a[i] + b[j] > x && j >= 0) j--; //若和小于x，则不必再找
    if( a[i] + b[j] == x) cout<< i<< ' '<< j;
}

  也可用将其中一个数组建立$hash$表，第二个数组根据它们关于$x$的互补关系查找哈希表。

1
2
3
4
5
6
7
8
9
10
unordered_map<int, int> ha;
for(int i = 0; i < n; i++){
    cin>>t;
    ha[t] = i; //数值-位置hash
}
for(int i = 0; i < m; i++){
    cin>> t; 
    if( ha.count(x - t) != 0) //查找成功
       cout<< ha[x - t] << ' ' << i;
}

离散化

  1. 区间和

  例如一个无限长的数轴，每次在某一位置上加c，再询问其某段区间的和。可以将其地址离散保存，再对地址进行排序后，后面的加c和前缀和都通过二分查询这个离散地址来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int N = 3e5+10;
int n, m;
int a[N], s[N];
vector<int> av;
vector< pair<int, int>> add, query;

int binfind(int x){
    int l = 0, r = av.size()-1;
    while(l<r){
        int mid = l + r >> 1;
        if(av[mid] >= x) r = mid;
        else l = mid+1;
    }
    return r+1;
}

int main(){
    cin>> n>> m;
    for(int i = 0; i < n; i++){
        int x, c;
        cin>> x>> c;
        add.push_back({x, c});
        av.push_back(x);  //地址
    }
    
    for(int i = 0; i < m; i++){
        int l, r;
        cin>> l>> r;
        query.push_back({l, r});
        av.push_back(l);
        av.push_back(r);
    }
    
    //对地址排序
    sort(av.begin(), av.end());
    
    //地址去重
    av.erase(unique(av.begin(), av.end()), av.end());
    
    for(auto item:add){
        int x = binfind(item.first);  //在av地址中去查找
        a[x] += item.second;
    }
    
    //前缀和
    for(int i = 1; i <= av.size(); i++){
        s[i] = s[i-1] + a[i] ;
    }
    
    for(auto item:query){
        int l = binfind(item.first), r = binfind(item.second);
        cout<< s[r] - s[l-1] << endl;
    }
    return 0 ;
}
  1. 区间合并

  只需将区间左边界排序，依次比较前面区间的ed与后面区间的st和ed的关系，它们只有三种关系，按情况对其进行更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
using  namespace std;

vector< pair<int, int>> pa;

int  main(){
    int n, count = 0; 
    cin >> n;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        pa.push_back({l, r});
    }
    
    sort(pa.begin(), pa.end());
    
    int start = -2e9, end = -2e9;
    for(auto it:pa){  //分情况，只有两种情况需要变更
        if(it.first <= end && it.second > end) end = it.second;
        else if(it.first > end) {
            start = it.first, end = it.second;
            count ++;
        }
    }
    cout << count;
}